package com.agile.leetcode.array.sum.sort;

import java.util.Arrays;

/**
 * 快排
 * @Author:ChenZhangKun
 * @Date: 2020/7/25 21:10
 */
public class QuickSortPractice {
    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 8, 9, 4, 5, 8, 9, 10, 45, 33, 63, 5, 8, 9, 62, 48, 5, 78, 5, 2659, 295, 4, 5};
        //输出原数组
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        //输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr){
        int left=0;
        int right=arr.length-1;
        quickSort(left,right,arr);
    }
    public static void quickSort(int left,int right,int[] arr){
        if (left<right){
            int partition = partition(left, right, arr);
            // 左递归
            quickSort(left,partition-1,arr);
            // 右递归
            quickSort(partition+1,right,arr);
        }
    }
    public static int partition(int left,int right,int[] arr){
        // 左指针
        int i=left;
        // 右指针
        int j=right;
        // 第一个坑位
        int x=arr[i];
        while (i<j){
            while (i<j&&arr[j]>=x){
                j--;
            }
            if (i<j&&x>=arr[j]){
                // 交换位置
               arr[i]=arr[j];
               i++;
            }
            while (i<j&&arr[i]<x){
                i++;
            }
            if (i<j&&arr[i]>=x){
                arr[j]=arr[i];
                j--;
            }
        }
        arr[i]=x;
        return i;
    }
}
